package com.heima.leetcode.practice;

/**
 * leetcode 76. 最小覆盖子串
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/19 10:34
 */
public class E76 {
    static int start; // 记录最短覆盖子串的起始位置，包含
    static int end; // 记录最短覆盖子串的结束位置，包含

    /**
     * <h3>方法一：移动窗口法，也就是双指针</h3>
     * @param s 原始字符串
     * @param t 目标字符串
     * @return 最短覆盖子串
     */
    public String minWindow(String s, String t) {
        start = 0; // 记录最短覆盖子串的起始位置。包含
        end = Integer.MAX_VALUE; // 记录最短覆盖子串的结束位置，包含
        char[] source = s.toCharArray(); // 源字符串
        char[] target = t.toCharArray(); // 目标字符串
        int[] sourceCount = new int[128]; // 源字符串中每个字符出现的次数
        int[] targetCount = new int[128]; // 目标字符串中每个字符出现的次数
        int passTotal = 0, passed = 0; // 目标字符串中不同字符的总数，一个字符计数一次

         // 统计目标字符串 t 中每个字符的出现次数
        for (char c : target) {
            targetCount[c]++;
        }

        // 统计 t 中不同字符的数量，一个字符计数一次
        for (int i : targetCount) {
            if (i > 0){
                passTotal++;
            }
        }

        // 滑动窗口，都是包含
        int i = 0, j = 0;
        while (j < source.length){
            // 右侧元素入窗口，统计passed，也就是目标字符串中多少个字符已经全部出现了
            char right = source[j++];
            sourceCount[right]++;
            if (sourceCount[right] == targetCount[right]){
                passed++;
            }

            // 如果passed == passTotal，说明窗口中已经包含了所有目标字符串中的字符，可以开始移动左侧指针，缩小窗口
            while (passed == passTotal){
                // 缩小窗口
                char left = source[i++];
                sourceCount[left]--;
                if (sourceCount[left] < targetCount[left]){
                    passed--;
                }

                // 缩小的同时判断是否是最短覆盖子串
                if (passed != passTotal){
                    if (j - i < end - start){
                        start = i - 1; // start包含，所以要-1，把前面加的减回来
                        end = j - 1; // end包含，所以要-1，把前面加的减回来
                    }
                }
            }
        }
        // 返回结果
        return end - start == Integer.MAX_VALUE ? "" : s.substring(start, end + 1);
    }
}
